#include <iostream>

using namespace std;

// 151. 反转字符串中的单词
// 给你一个字符串 s ，请你反转字符串中 单词 的顺序。
// 示例 1：
// 输入：s = "the sky is blue"
// 输出："blue is sky the"
// 示例 2：
// 输入：s = "  hello world  "
// 输出："world hello"
class Solution {
public:
    string reverseWords(string s) {
        reverse(s.begin(),s.end()); // 反转整个字符串
        int i = 0;      // i 是结果字符串的下标
        for(int start = 0; start < s.size(); start++) {
            if(s[start] != ' ') {   // 找到第1个非空格字符
                if(i != 0) s[i++] = ' '; // 单词之间加个空格
                int end = start;    // 循环遍历至单词的末尾
                while(end < s.size() && s[end] != ' ')
                    s[i++] = s[end++];  // 将单词前移
                reverse(s.begin() + i - (end - start), s.begin() + i);  // 反转单词
                start = end;    // 更新start，反转下一个单词
            }
        }
        s.erase(s.begin() + i, s.end());    // 删除末尾部分
        return s;
    }
};
int main() {
    cout << Solution().reverseWords("the sky is blue") << endl;
    cout << Solution().reverseWords("  hello world  ") << endl;
    cout << Solution().reverseWords("a good   example") << endl;
    return 0;
}
